const isInBetween = (a, b, c) => {
  // 如果b几乎等于a或c，返回false.为了避免浮点运行时两值几乎相等，但存在相差0.00000...0001的这种情况出现使用下面方式进行避免
  if (Math.abs(a - b) < 0.000001 || Math.abs(b - c) < 0.000001) {
    return false;
  }

  return (a < b && b < c) || (c < b && b < a);
};
class Vector {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
  // 向量叉乘
  cross(v) {
    return this.x * v.y - this.y * v.x;
  }
  // 向量点乘
  dot(v) {
    return this.x * v.x + this.y * v.y;
  }
  // 向量减法
  sub(v) {
    return new Vector(this.x - v.x, this.y - v.y);
  }
}
class Point {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
  // 重载减法运算符
  sub(p) {
    return new Point(this.x - p.x, this.y - p.y);
  }
}
const eps = 1e-6;
// 比较两个数值的大小关系
function dcmp(x) {
  if (Math.abs(x) < eps) return 0;
  else return x < 0 ? -1 : 1;
}
// 判断点是否在线段上
function OnSegment(P1, P2, Q) {
  return (
    dcmp(P1.sub(Q).cross(P2.sub(Q))) == 0 && dcmp(P1.sub(Q).dot(P2.sub(Q))) <= 0
  );
}
// 示例多边形坐标
let polygon = [
  [1, 1],
  [1, 3],
  [3, 3],
  [3, 1],
];
// 测试点
let testX = 2,
  testY = 2;
// 判断点是否在多边形内
let isInside = pointInPolygon(testX, testY, polygon);
console.log(`点 (${testX}, ${testY}) 是否在多边形${JSON.stringify(polygon)}内: ${isInside}`);
// 转角法
export function pointInPolygon(x, y, polygon, allowOnSegment = true) {
  let wn = 0;
  let P = new Point(x, y);
  const polygonPointArr = polygon.map((item) => new Vector(...item));
  for (
    let i = 0, j = polygonPointArr.length - 1;
    i < polygonPointArr.length;
    j = i++
  ) {
    let P1 = polygonPointArr[j];
    let P2 = polygonPointArr[i];
    if (OnSegment(P1, P2, P)) return allowOnSegment;
    let V1 = P2.sub(P1);
    let V2 = P.sub(P1);
    let k = dcmp(V1.cross(V2));
    let d1 = dcmp(P1.y - P.y);
    let d2 = dcmp(P2.y - P.y);
    if (k > 0 && d1 <= 0 && d2 > 0) wn--;
    if (k < 0 && d1 > 0 && d2 <= 0) wn++;
  }
  return wn !== 0;
}
// 辅助函数 检查两个线是否交叉
export const isIntersect = (line1, line2) => {
  console.log(305, line1, line2);
  // 转换成一般式: Ax+By = C
  let a1 = line1.y2 - line1.y1;
  let b1 = line1.x1 - line1.x2;
  let c1 = a1 * line1.x1 + b1 * line1.y1;

  //转换成一般式: Ax+By = C
  let a2 = line2.y2 - line2.y1;
  let b2 = line2.x1 - line2.x2;
  let c2 = a2 * line2.x1 + b2 * line2.y1;

  // 计算交点
  let d = a1 * b2 - a2 * b1;
  // 当d==0时，两线平行
  if (d == 0) {
    return false;
  } else {
    let x = (b2 * c1 - b1 * c2) / d;
    let y = (a1 * c2 - a2 * c1) / d;

    // 检测交点是否在两条线段上
    if (
      (isInBetween(line1.x1, x, line1.x2) ||
        isInBetween(line1.y1, y, line1.y2)) &&
      (isInBetween(line2.x1, x, line2.x2) || isInBetween(line2.y1, y, line2.y2))
    ) {
      console.log(331);
      return true;
    }
  }
  console.log(335);

  return false;
};
// 示例用法
// let polygon = [
//   { x: 1, y: 1 },
//   { x: 2, y: 3 },
//   { x: 4, y: 2 },
//   { x: 3, y: 1 }
// ];

// if (polygonHasIntersectingLinesAllowingVertices(polygon)) {
//   console.log("多边形存在交叉线（允许交叉点存在）.");
// } else {
//   console.log("多边形不存在交叉线（允许交叉点存在）.");
// }

export function polygonHasIntersectingLinesAllowingVertices(polygon) {
  for (let i = 0; i < polygon.length; i++) {
    let edge1 = { start: polygon[i], end: polygon[(i + 1) % polygon.length] };
    for (let j = i + 2; j < polygon.length; j++) {
      let edge2 = { start: polygon[j], end: polygon[(j + 1) % polygon.length] };
      if (i === 0 && j === polygon.length - 1) continue; // Skip adjacent edges
      if (segmentsIntersect(edge1, edge2, false)) {
        return true; // Polygon has intersecting lines
      }
    }
  }
  return false; // Polygon does not have intersecting lines
}

// 判断两条线段是否相交
// 示例用法
// let segments = [
//   { start: { x: 1, y: 1 }, end: { x: 4, y: 4 } },
//   { start: { x: 2, y: 2 }, end: { x: 5, y: 5 } },
//   { start: { x: 6, y: 6 }, end: { x: 8, y: 8 } },
// ];

// if (multipleSegmentsIntersect(segments)) {
//   console.log("线段相交.");
// } else {
//   console.log("线段不相交.");
// }
// notAllowingVertices是否允许线段存在交叉点
function segmentsIntersect(seg1, seg2, notAllowingVertices = true) {
  function direction(p1, p2, p3) {
    return (p3.x - p1.x) * (p2.y - p1.y) - (p3.y - p1.y) * (p2.x - p1.x);
  }

  let d1 = direction(seg1.start, seg1.end, seg2.start);
  let d2 = direction(seg1.start, seg1.end, seg2.end);
  let d3 = direction(seg2.start, seg2.end, seg1.start);
  let d4 = direction(seg2.start, seg2.end, seg1.end);
  if (
    (d1 === 0 && onSegment(seg1.start, seg1.end, seg2.start)) ||
    (d2 === 0 && onSegment(seg1.start, seg1.end, seg2.end)) ||
    (d3 === 0 && onSegment(seg2.start, seg2.end, seg1.start)) ||
    (d4 === 0 && onSegment(seg2.start, seg2.end, seg1.end))
  ) {
    return notAllowingVertices; // 线段有共线点且重叠
  }
  // 线段不相交
  return (
    ((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
    ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))
  );
}

function onSegment(p1, p2, p3) {
  return (
    Math.min(p1.x, p2.x) <= p3.x &&
    p3.x <= Math.max(p1.x, p2.x) &&
    Math.min(p1.y, p2.y) <= p3.y &&
    p3.y <= Math.max(p1.y, p2.y)
  );
}

export function multipleSegmentsIntersect(segments) {
  console.log(segments, "segments");
  for (let i = 0; i < segments.length; i++) {
    for (let j = i + 1; j < segments.length; j++) {
      if (segmentsIntersect(segments[i], segments[j])) {
        return true; // 线段相交
      }
    }
  }
  return false; // 线段不相交
}
